#include<iostream>
#include<vector>
#include<string>
using namespace std;




int countSubstrings(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n));
    int count = 0;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j])
                dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
            if (dp[i][j])
                count++;
        }
    }
    return count;
}


int main()
{
    string s = "aaa";
    countSubstrings(s);
    return 0;
}